package com.base.string;

/**
 * TODO(306. 累加数)
 * 累加数 是一个字符串，组成它的数字可以形成累加序列。
 * <p>
 * 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
 * <p>
 * 给你一个只包含数字'0'-'9'的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 说明：累加序列里的数 不会 以 0 开头，所以不会出现1, 2, 03 或者1, 02, 3的情况。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/additive-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2022年01月10日 11:35
 */
public class IsAdditiveNumber {

    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int secondStart = 1; secondStart < n - 1; secondStart++) {
            // 累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况
            if (num.charAt(0) == '0' && secondStart != 1) {
                break;
            }
            for (int secondEnd = secondStart; secondEnd < n - 1; secondEnd++) {
                // 累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况
                if (num.charAt(secondStart) == '0' && secondEnd != secondStart) {
                    break;
                }
                if(isValid(secondStart,secondEnd,num)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断当前划分是否有效
     * @param secondStart
     * @param secondEnd
     * @param num
     * @return
     */
    public boolean isValid(int secondStart,int secondEnd,String num) {
        int n = num.length();
        int firstStart = 0,firstEnd = secondStart-1;
        while (secondEnd<=n-1){
            String first = num.substring(firstStart,firstEnd+1);
            String second = num.substring(secondStart,secondEnd+1);
            String third = stringAdd(first,second);
            int thirdStart = secondEnd+1;
            int thirdEnd = secondEnd+third.length();
            if (thirdEnd>n-1||!third.equals(num.substring(thirdStart,thirdEnd+1))){
                return false;
            }
            if(thirdEnd==n-1){
                return true;
            }
            firstStart = secondStart;
            firstEnd = secondEnd;
            secondStart = thirdStart;
            secondEnd = thirdEnd;
        }
        return false;
    }

    /**
     * 字符串数字相加
     *
     * @param a
     * @param b
     * @return
     */
    public String stringAdd(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int aEnd = a.length() - 1, bEnd = b.length() - 1;
        int cur = 0, carry = 0;
        while (aEnd >= 0 || bEnd >= 0 || carry > 0) {
            cur = carry;
            if (aEnd >= 0) {
                cur += (a.charAt(aEnd) - '0');
                aEnd--;
            }
            if (bEnd >= 0) {
                cur += (b.charAt(bEnd) - '0');
                bEnd--;
            }
            carry = cur / 10;
            cur = cur % 10;
            sb.append((char) (cur + '0'));
        }
        sb.reverse();
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new IsAdditiveNumber().isAdditiveNumber("112358"));
    }
}
